{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Build Sturdy Brick Wall"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: buildWall"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #建造坚实的砖墙的方法数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数&nbsp;<code>height</code>&nbsp;与<code>width</code>&nbsp;，表示你要建造的砖墙的高和宽。再给你一个下标从 <strong>0</strong> 开始的数组 <code>bricks</code> ，其中第 <code>i</code> 块砖的高度是 <code>1</code> ，宽度为 <code>bricks[i]</code> 。每种砖的数量都是 <strong>无限 </strong>的，并且砖 <strong>不可以</strong> 进行旋转。</p>\n",
    "\n",
    "<p>墙的每一行必须正好&nbsp;<code>width</code> 单位长。为了让墙体<strong> 坚实 </strong>，除了在首尾的位置，相邻的行砖缝<strong> 不能 </strong>在同一个位置。</p>\n",
    "\n",
    "<p>请你返回建造坚实的砖墙的方法数，由于答案可能很大，需要对 <code>10<sup>9</sup> + 7</code><strong> 取余</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/02/20/image-20220220190749-1.png\" style=\"width: 919px; height: 250px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>height = 2, width = 3, bricks = [1,2]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>前两图中的两种方法是建造一座坚实砖墙的唯二的方法。注意，第三幅图所展示的不是坚实的砖墙，因为相邻的行在中间的连接点位置相同。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>height = 1, width = 1, bricks = [5]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>无法建造符合题目要求的砖墙，因为仅有的砖的长度比墙还要长。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= height &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= width &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= bricks.length &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= bricks[i] &lt;= 10</code></li>\n",
    "\t<li><code>bricks</code>&nbsp;中所有数字<strong> 互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-build-sturdy-brick-wall](https://leetcode.cn/problems/number-of-ways-to-build-sturdy-brick-wall/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-build-sturdy-brick-wall](https://leetcode.cn/problems/number-of-ways-to-build-sturdy-brick-wall/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n3\\n[1,2]', '1\\n1\\n[5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        bricks.sort()\n",
    "        dp = [set() for _ in range(width + 1)]\n",
    "        dp[0].add(tuple())\n",
    "        for x in bricks:\n",
    "            for i in range(x, width + 1):\n",
    "                for pre in dp[i - x]:\n",
    "                    dp[i].add(pre + (x,))\n",
    "        nodes = set()\n",
    "        for tp in dp[-1]:\n",
    "            for item in permutations(tp, len(tp)):\n",
    "                nodes.add(tuple(item))\n",
    "\n",
    "        state = [set(list(accumulate(tp))[:-1]) for tp in nodes]\n",
    "        n = len(state)\n",
    "\n",
    "        edge = [set() for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if not state[i].intersection(state[j]):\n",
    "                    edge[i].add(j)\n",
    "                    edge[j].add(i)\n",
    "\n",
    "        dp1 = [1] * n\n",
    "        for _ in range(height - 1):\n",
    "            dp2 = [sum(dp1[j] for j in edge[i]) % mod for i in range(n)]\n",
    "            dp1 = dp2[:]\n",
    "        return sum(dp1) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 记忆化dfs爆搜\n",
    "# index、preSplit、curSplit、curWidth分别表示当前行数、前一行砖块结尾的分割点、当前行砖块结尾的分割点、当前行已经填充的宽度 时间、空间复杂度即搜索的可能数O(nm4^n)\n",
    "from functools import lru_cache\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "\n",
    "\n",
    "class Solution1:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        \"\"\"相邻两行分割点不能重合\"\"\"\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, preSplit: int, curSplit: int, curWidth: int) -> int:\n",
    "            if index == height:\n",
    "                return 1\n",
    "\n",
    "            if curWidth == width:\n",
    "                return dfs(index + 1, curSplit, 0, 0) % MOD\n",
    "\n",
    "            res = 0\n",
    "            for choose in bricks:\n",
    "                nextWidth = curWidth + choose\n",
    "                if nextWidth > width:\n",
    "                    break\n",
    "\n",
    "                nextSplit = curSplit\n",
    "                if nextWidth != width:\n",
    "                    nextSplit |= 1 << nextWidth\n",
    "\n",
    "                if nextSplit & preSplit:\n",
    "                    continue\n",
    "\n",
    "                res += dfs(index, preSplit, nextSplit, nextWidth)\n",
    "                res %= MOD\n",
    "\n",
    "            return res\n",
    "\n",
    "        bricks = sorted(bricks)\n",
    "        res = dfs(0, 0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "# 预处理每行可能的状态后，相邻行间进行dp的解法，每行状态用状压，dp用字典记录比较方便\n",
    "from collections import defaultdict\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        def dfs(curWidth: int, state: int) -> None:\n",
    "            if curWidth > width:\n",
    "                return\n",
    "\n",
    "            if curWidth == width:\n",
    "                availableStates.add(state)\n",
    "                return\n",
    "\n",
    "            for choose in bricks:\n",
    "                nextWidth = curWidth + choose\n",
    "                nextState = state\n",
    "                if nextWidth != width:\n",
    "                    nextState |= 1 << (nextWidth)\n",
    "\n",
    "                dfs(nextWidth, nextState)\n",
    "\n",
    "        bricks = sorted(bricks)\n",
    "        availableStates = set()\n",
    "        dfs(0, 0)\n",
    "\n",
    "        dp = [defaultdict(int) for _ in range(height)]\n",
    "        for state in availableStates:\n",
    "            dp[0][state] = 1\n",
    "\n",
    "        for i in range(1, height):\n",
    "            for state in availableStates:\n",
    "                for preState in dp[i - 1].keys():\n",
    "                    if not state & preState:\n",
    "                        dp[i][state] += dp[i - 1][preState]\n",
    "                        dp[i][state] %= MOD\n",
    "\n",
    "        res = 0\n",
    "        for state in dp[-1].keys():\n",
    "            res += dp[-1][state]\n",
    "            res %= MOD\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        #if width==min(bricks):\n",
    "        #    return 1\n",
    "        bricks.sort()\n",
    "        mod=10**9+7\n",
    "        while bricks and bricks[-1]>width:\n",
    "            bricks.pop()\n",
    "        if not bricks:\n",
    "            return 0\n",
    "        if len(bricks)==1:\n",
    "            if height==1:\n",
    "                return 1\n",
    "            if bricks[0]!=width:\n",
    "                return 0\n",
    "            return 1\n",
    "        line=[]\n",
    "        #print(line)\n",
    "        def dfs(x,mark):\n",
    "            #print(x,mark)\n",
    "            if x==width:\n",
    "                mark-=1<<width\n",
    "                line.append(mark)\n",
    "                return \n",
    "            if x>width:\n",
    "                return\n",
    "            for b in bricks:\n",
    "                dfs(x+b,mark+(1<<(x+b)))\n",
    "        dfs(0,0)\n",
    "        #for i in line:\n",
    "        #    print(str(bin(i)))\n",
    "        @cache\n",
    "        def dp(x,last):\n",
    "            if x==height:\n",
    "                return 1\n",
    "            ret=0\n",
    "            for i in line:\n",
    "                if i&last:\n",
    "                    continue\n",
    "                ret+=dp(x+1,i)\n",
    "            return ret%mod\n",
    "        return dp(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        if width==min(bricks):\n",
    "            return 1\n",
    "        bricks.sort()\n",
    "        mod=10**9+7\n",
    "        while bricks and bricks[-1]>width:\n",
    "            bricks.pop()\n",
    "        if not bricks:\n",
    "            return 0\n",
    "        if len(bricks)==1:\n",
    "            if height==1:\n",
    "                return 1\n",
    "            if len(bricks)!=width:\n",
    "                return 0\n",
    "            return 1\n",
    "        line=[]\n",
    "        def dfs(x,mark):\n",
    "            if x==width:\n",
    "                mark-=1<<width\n",
    "                line.append(mark)\n",
    "                return \n",
    "            if x>width:\n",
    "                return\n",
    "            for b in bricks:\n",
    "                dfs(x+b,mark+(1<<(x+b)))\n",
    "        dfs(0,0)\n",
    "        #for i in line:\n",
    "        #    print(str(bin(i)))\n",
    "        @cache\n",
    "        def dp(x,last):\n",
    "            if x==height:\n",
    "                return 1\n",
    "            ret=0\n",
    "            for i in line:\n",
    "                if i&last:\n",
    "                    continue\n",
    "                ret+=dp(x+1,i)\n",
    "            return ret%mod\n",
    "        return dp(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        #if width==min(bricks):\n",
    "        #    return 1\n",
    "        bricks.sort()\n",
    "        mod=10**9+7\n",
    "        while bricks and bricks[-1]>width:\n",
    "            bricks.pop()\n",
    "        if not bricks:\n",
    "            return 0\n",
    "        if len(bricks)==1:\n",
    "            if width%bricks[0]!=0:\n",
    "                return 0\n",
    "            if height==1:\n",
    "                return 1\n",
    "            if bricks[0]!=width:\n",
    "                return 0\n",
    "            return 1\n",
    "        line=[]\n",
    "        #print(line)\n",
    "        def dfs(x,mark):\n",
    "            #print(x,mark)\n",
    "            if x==width:\n",
    "                mark-=1<<width\n",
    "                line.append(mark)\n",
    "                return \n",
    "            if x>width:\n",
    "                return\n",
    "            for b in bricks:\n",
    "                dfs(x+b,mark+(1<<(x+b)))\n",
    "        dfs(0,0)\n",
    "        #for i in line:\n",
    "        #    print(str(bin(i)))\n",
    "        @cache\n",
    "        def dp(x,last):\n",
    "            if x==height:\n",
    "                return 1\n",
    "            ret=0\n",
    "            for i in line:\n",
    "                if i&last:\n",
    "                    continue\n",
    "                ret+=dp(x+1,i)\n",
    "            return ret%mod\n",
    "        return dp(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        #if width==min(bricks):\n",
    "        #    return 1\n",
    "        bricks.sort()\n",
    "        mod=10**9+7\n",
    "        while bricks and bricks[-1]>width:\n",
    "            bricks.pop()\n",
    "        if not bricks:\n",
    "            return 0\n",
    "        if len(bricks)==1:\n",
    "            if height==1:\n",
    "                return 1\n",
    "            if bricks[0]!=width:\n",
    "                return 0\n",
    "            return 1\n",
    "        line=[]\n",
    "        print(line)\n",
    "        def dfs(x,mark):\n",
    "            print(x,mark)\n",
    "            if x==width:\n",
    "                mark-=1<<width\n",
    "                line.append(mark)\n",
    "                return \n",
    "            if x>width:\n",
    "                return\n",
    "            for b in bricks:\n",
    "                dfs(x+b,mark+(1<<(x+b)))\n",
    "        dfs(0,0)\n",
    "        #for i in line:\n",
    "        #    print(str(bin(i)))\n",
    "        @cache\n",
    "        def dp(x,last):\n",
    "            if x==height:\n",
    "                return 1\n",
    "            ret=0\n",
    "            for i in line:\n",
    "                if last!=0 and  i&last:\n",
    "                    continue\n",
    "                ret+=dp(x+1,i)\n",
    "            return ret%mod\n",
    "        return dp(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        #if width==min(bricks):\n",
    "        #    return 1\n",
    "        bricks.sort()\n",
    "        mod=10**9+7\n",
    "        while bricks and bricks[-1]>width:\n",
    "            bricks.pop()\n",
    "        if not bricks:\n",
    "            return 0\n",
    "        if len(bricks)==1:\n",
    "            if height==1:\n",
    "                return 1\n",
    "            if bricks[0]!=width:\n",
    "                return 0\n",
    "            return 1\n",
    "        line=[]\n",
    "        print(line)\n",
    "        def dfs(x,mark):\n",
    "            print(x,mark)\n",
    "            if x==width:\n",
    "                mark-=1<<width\n",
    "                line.append(mark)\n",
    "                return \n",
    "            if x>width:\n",
    "                return\n",
    "            for b in bricks:\n",
    "                dfs(x+b,mark+(1<<(x+b)))\n",
    "        dfs(0,0)\n",
    "        #for i in line:\n",
    "        #    print(str(bin(i)))\n",
    "        @cache\n",
    "        def dp(x,last):\n",
    "            if x==height:\n",
    "                return 1\n",
    "            ret=0\n",
    "            for i in line:\n",
    "                if  i&last:\n",
    "                    continue\n",
    "                ret+=dp(x+1,i)\n",
    "            return ret%mod\n",
    "        return dp(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        bricks = [x for x in bricks if x <= width]\n",
    "        bricks = set(bricks)\n",
    "        n = width - 1\n",
    "\n",
    "        def check(x):\n",
    "            pre = -1\n",
    "            for i in range(n):\n",
    "                if (x >> i) & 1:\n",
    "                    tmp = i - pre\n",
    "                    if tmp not in bricks:\n",
    "                        return False\n",
    "                    pre = i\n",
    "            if n - pre not in bricks:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        tot = []\n",
    "        for i in range(1 << n):\n",
    "            if check(i):\n",
    "                tot.append(i)\n",
    "        g = defaultdict(list)\n",
    "        ln = len(tot)\n",
    "        if not ln:\n",
    "            return 0\n",
    "        for i in range(ln):\n",
    "            for j in range(i + 1, ln):\n",
    "                if tot[i] & tot[j] == 0:\n",
    "                    g[i].append(j)\n",
    "                    g[j].append(i)\n",
    "        if 0 in tot:\n",
    "            g[0].append(0)\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def f(i, layer):\n",
    "            if layer == height - 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for nxt in g[i]:\n",
    "                res += f(nxt, layer + 1)\n",
    "            return res % mod\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(ln):\n",
    "            ans += f(i, 0)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :param height:\n",
    "        :param width:\n",
    "        :param bricks:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def yield_ans(cur_w, offset, prev_limit = frozenset()):\n",
    "            ret = []\n",
    "            if cur_w == 0:\n",
    "                return [[]]\n",
    "            for i in bricks:\n",
    "                dec1 = cur_w - i\n",
    "                if dec1 >= 0 and dec1 not in prev_limit:\n",
    "                    for j in yield_ans(dec1, offset+i, prev_limit):\n",
    "                        ret.append([width - i - offset] + j)\n",
    "            return ret\n",
    "\n",
    "\n",
    "        def oper_ans(ans):\n",
    "            ans.pop()\n",
    "            return ans\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_build_cnt(level, prev_limit):\n",
    "            if level == height:\n",
    "                return 1\n",
    "            ret = 0\n",
    "            for i in yield_ans(width, 0, prev_limit):\n",
    "                curx = i\n",
    "                if curx and curx[-1] == 0:\n",
    "                    curx.pop()\n",
    "                x1 = 1\n",
    "                x1 *= get_build_cnt(level + 1, frozenset(curx))\n",
    "                ret += x1\n",
    "\n",
    "            return ret % (10**9 + 7)\n",
    "\n",
    "        ret = get_build_cnt(0, frozenset())\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :param height:\n",
    "        :param width:\n",
    "        :param bricks:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def yield_ans(cur_w, offset, prev_limit = frozenset()):\n",
    "            ret = []\n",
    "            if cur_w == 0:\n",
    "                return [[]]\n",
    "            for i in bricks:\n",
    "                dec1 = cur_w - i\n",
    "                if dec1 >= 0 and dec1 not in prev_limit:\n",
    "                    for j in yield_ans(dec1, offset+i, prev_limit):\n",
    "                        ret.append([width - i - offset] + j)\n",
    "            return ret\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_build_cnt(level, prev_limit):\n",
    "            if level == height:\n",
    "                return 1\n",
    "            ret = 0\n",
    "            for i in yield_ans(width, 0, prev_limit):\n",
    "                curx = i\n",
    "                if curx and curx[-1] == 0:\n",
    "                    curx.pop()\n",
    "                x1 = 1\n",
    "                x1 *= get_build_cnt(level + 1, frozenset(curx))\n",
    "                ret += x1\n",
    "\n",
    "            return ret % (10**9 + 7)\n",
    "\n",
    "        return get_build_cnt(0, frozenset())\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 记忆化dfs爆搜\n",
    "# index、preSplit、curSplit、curWidth分别表示当前行数、前一行砖块结尾的分割点、当前行砖块结尾的分割点、当前行已经填充的宽度 时间、空间复杂度即搜索的可能数O(nm4^n)\n",
    "from functools import lru_cache\n",
    "from typing import List\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        \"\"\"相邻两行分割点不能重合\"\"\"\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, preSplit: int, curSplit: int, curWidth: int) -> int:\n",
    "            if index == height:\n",
    "                return 1\n",
    "            if curWidth == width:\n",
    "                return dfs(index + 1, curSplit, 0, 0) % MOD\n",
    "\n",
    "            res = 0\n",
    "            for choose in bricks:\n",
    "                nextWidth = curWidth + choose\n",
    "                if nextWidth > width:\n",
    "                    break\n",
    "\n",
    "                nextSplit = curSplit\n",
    "                if nextWidth != width:\n",
    "                    nextSplit |= 1 << nextWidth\n",
    "                if nextSplit & preSplit:\n",
    "                    continue\n",
    "\n",
    "                res += dfs(index, preSplit, nextSplit, nextWidth)\n",
    "                res %= MOD\n",
    "\n",
    "            return res\n",
    "\n",
    "        bricks = sorted(bricks)\n",
    "        res = dfs(0, 0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from typing import List\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def buildWall(self, height: int, width: int, bricks: List[int]) -> int:\n",
    "        \"\"\"相邻两行分割点不能重合\"\"\"\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, preSplit: int, curSplit: int, curWidth: int) -> int:\n",
    "            if index == height:\n",
    "                return 1\n",
    "            if curWidth == width:\n",
    "                return dfs(index + 1, curSplit, 0, 0) % MOD\n",
    "\n",
    "            res = 0\n",
    "            for choose in bricks:\n",
    "                nextWidth = curWidth + choose\n",
    "                if nextWidth > width:\n",
    "                    break\n",
    "\n",
    "                nextSplit = curSplit\n",
    "                if nextWidth != width:\n",
    "                    nextSplit |= 1 << nextWidth\n",
    "                if nextSplit & preSplit:\n",
    "                    continue\n",
    "\n",
    "                res += dfs(index, preSplit, nextSplit, nextWidth)\n",
    "                res %= MOD\n",
    "\n",
    "            return res\n",
    "\n",
    "        bricks = sorted(bricks)\n",
    "        res = dfs(0, 0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
